//摆动序列（medium）: https://leetcode.cn/problems/wiggle-subsequence/
class Solution
{
public:
	int wiggleMaxLength(vector<int>& nums)
	{
		int n = nums.size();
		if (n < 2)
		{
			return n;
		}
		int ret = 0, left = 0;
		for (int i = 0; i < n - 1; i++)
		{
			int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
			if (right == 0)
			{
				continue;
			}// 如果⽔平，直接跳过
			if (right * left <= 0)
			{
				ret++; // 累加波峰或者波⾕
			}
			left = right;
			
		}
		return ret + 1;
	}
};

//最⻓递增⼦序列（medium）: https://leetcode.cn/problems/longest-increasing-subsequence/description/
class Solution
{
public:
	int lengthOfLIS(vector<int>& nums)
	{
		int n = nums.size();
		vector<int> ret;
		ret.push_back(nums[0]);
		for (int i = 1; i < n; i++)
		{
			if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放
			{
				ret.push_back(nums[i]);
			}
			else
			{
				// ⼆分插⼊位置
				int left = 0, right = ret.size() - 1;
				while (left < right)
				{
					int mid = (left + right) >> 1;
					if (ret[mid] < nums[i])
					{
						left = mid + 1;
					}
					else
					{
						right = mid;
					}
				}
				ret[left] = nums[i]; // 放在 left 位置上
			}
		}
		return ret.size();
	}
};